package com.algomypractice.binary;

/**
 * @author: ZhouBert
 * @date: 2019/6/24
 * @description: 二分查找
 */
public class Search {

	//region	不重复数据的查找元素（简单情况二分查找）

	/**
	 * 二分查找
	 *
	 * @param arr   待查找数组(已经排好序)
	 * @param n     数组长度
	 * @param value 寻找的值
	 * @return
	 */
	public static int bsearch(int[] arr, int n, int value) {
		int low = 0;
		int high = n - 1;
		int mid;
		//while (low < high)///这种是错的，没有具体定位到最终值，应该得判断到最后的值，然后去匹配，如果匹配不到就返回-1
		while (low <= high) {
			mid = (low + high) / 2;
			if (arr[mid] == value) {
				return mid;
			} else if (arr[mid] < value) {
				low = mid + 1;
			} else {
				high = mid - 1;
			}
		}

		return -1;
	}

	/**
	 * 通过递归进行二分查找
	 *
	 * @param arr
	 * @param low
	 * @param low
	 * @param value
	 * @return
	 */
	public static int bssearchByRecursion(int[] arr, int low, int high, int value) {
		if (low > high) {
			return -1;
		}
		int mid = low + ((high - low) >> 1);
		if (arr[mid] == value) {
			return mid;
		} else if (arr[mid] < value) {
			return bssearchByRecursion(arr, mid + 1, high, value);
		} else {
			return bssearchByRecursion(arr, low, mid - 1, value);
		}
	}

	//endregion


	//region	重复数据的二分查找(查找同值第一个的索引)

	/**
	 * 查找数据的第一个值
	 *
	 * @param arr   待查找数组
	 * @param n     数组长度
	 * @param value
	 * @return
	 */
	public static int bssearchFirst(int[] arr, int n, int value) {
		int low = 0;
		int high = n - 1;
		int mid;
		while (low <= high) {
			mid = low + ((high - low) >> 1);
			if (arr[mid] < value) {
				low = mid + 1;
			}
			///当匹配到值时，需要向前二分
			else if (arr[mid] >= value) {
				high = mid - 1;
			}
		}
		///此时如果已经匹配到了相等的值时，low=high,并且 arr[low] = value	//需要排除 value > max 的情况,判断数组越界
		if (low < n && arr[low] == value) {
			return low;
		}
		return -1;
	}

	//endregion

	//region	重复数据的二分查找(查找同值最后一个的索引)

	public static int bssearchLast(int[] arr, int n, int value) {
		int low = 0;
		int high = n - 1;
		int mid;
		while (low <= high) {
			mid = low + ((high - low) >> 1);
			if (arr[mid] <= value) {
				low = mid + 1;
			} else {
				high = mid - 1;
			}
		}
		if (high > -1 && arr[high] == value) {
			return high;
		}
		return -1;
	}

	//endregion

	//region	重复数据的二分查找(查找第一个大于等于给定元素的索引)

	/**
	 * @param arr
	 * @param n
	 * @param value
	 * @return
	 */
	public static int bssearchFirstGET(int[] arr, int n, int value) {
		int low = 0;
		int high = n - 1;
		int mid;
		while (low <= high) {
			mid = low + ((high - low) >> 2);
			///当中间值大于等于给定元素时，需要向前二分，查找第一个大于等于给定元素
			if (arr[mid] >= value) {
				high = mid - 1;
			} else {
				low = mid + 1;
			}
		}
		if (low < n && arr[low] >= value) {
			return low;
		}
		return -1;
	}

	//endregion

	//region	重复数据的二分查找(查找最后一个小于等于给定元素的索引)

	public static int bssearchLastLET(int[] arr, int n, int value) {
		int low = 0;
		int high = n - 1;
		int mid;
		while (low <= high) {
			mid = low + ((high - low) >> 1);
			///当中间值小于等于给定元素，向后二分，直到找到最后
			if (arr[mid] <= value) {
				low = mid + 1;
			} else {
				high = mid - 1;
			}
		}
		if (high > -1 && arr[high] <= value) {
			return high;
		}
		return -1;
	}

	//endregion

	//region	不重复的 循环有序数组[4,5,6,1,2,3] 查找等值元素

	///我擦 这个思路有问题
	public static int bssearchLoop(int[] arr, int n, int value) {
		///朝右标志
		boolean forwardRight = true;
		if (arr[0] < value) {
			forwardRight = false;
		} else if (arr[0] == value) {
			return 0;
		}

		int low = 0;
		int high = n - 1;
		int mid;
		while (low <= high) {
			mid = low + ((high - low) >> 1);
			if (arr[mid] == value) {
				return mid;
			} else if (arr[mid] < value) {
				if (forwardRight) {
					low = mid + 1;
				} else {
					high = mid - 1;
				}
			} else {
				if (forwardRight) {

				}
			}
		}
		return -1;
	}

	public static int bssearchLoopArr(int[] arr, int n, int value) {
		int low = 0;
		int high = n - 1;
		int mid;
		while (low <= high) {
			mid = low + ((high - low) >> 1);
			if (arr[mid] == value) {
				return mid;
			}
			///枚举向后二分查找的情况 arr[low]<arr[mid] 说明单调递增//写一起不好判断
//			else if ((arr[low] < arr[mid] && (value >= arr[mid] || value < arr[high]))
//					|| (arr[low] > arr[mid] && value <= arr[high])) {
//				low = mid + 1;
//			} else {
//				high = mid - 1;
//			}
			//当转折点在右边
			else if (arr[low] < arr[mid]){
				//在单调区间时，进行左二分
				if (arr[low]<=value && value<arr[mid]){
					high=mid-1;
				}else{
					low=mid+1;
				}
			}else{
				//在单调区间时，进行右二分
				if (value>arr[mid]&& value<=arr[high]){
					low=mid+1;
				}else {
					high=mid-1;
				}
			}
		}
		return -1;
	}

	//endregion

	public static void main(String[] args) {
		int[] arr = new int[9];
		arr[0] = 1;
		arr[1] = 2;
		arr[2] = 5;
		arr[3] = 8;
		arr[4] = 8;
		arr[5] = 8;
		arr[6] = 9;
		arr[7] = 10;
		arr[8] = 11;
		///System.out.println(1e-7);

		///System.out.println(bsearch(arr, arr.length, 3));
		System.out.println(bssearchFirst(arr, arr.length, 8));
		System.out.println(bssearchLast(arr, arr.length, 8));

		System.out.println(bssearchFirstGET(arr, arr.length, 8));
		System.out.println(bssearchLastLET(arr, arr.length, 8));

		///循环有序数组 查找等值元素
		int[] loopArr = new int[6];
		loopArr[0] = 4;
		loopArr[1] = 5;
		loopArr[2] = 6;
		loopArr[3] = 1;
		loopArr[4] = 2;
		loopArr[5] = 3;

		System.out.println(bssearchLoopArr(loopArr, loopArr.length, 3));
		System.out.println(bssearchLoopArr(loopArr, loopArr.length, 4));
		System.out.println(bssearchLoopArr(loopArr, loopArr.length, 5));
		System.out.println(bssearchLoopArr(loopArr, loopArr.length, 6));
		System.out.println(bssearchLoopArr(loopArr, loopArr.length, 1));
		System.out.println(bssearchLoopArr(loopArr, loopArr.length, 2));
	}
}
